package algorthm.systemTraning.countSort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @className: CountSort
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/30 13:43
 */
public class CountSort {
    private static Logger logger = LoggerFactory.getLogger(CountSort.class);
    public static void sort(int[] array){
        if(null == array || array.length < 2){
            return ;
        }
        int max = 0 , min = 0 ;
        for(int i = 0 ; i < array.length ; i++){
            if(array[i] > max){
               max = array[i] ;
            }
            if(array[i] < min){
                min = array[i];
            }
        }
        int[] mid = new int[max - min + 1];
        for(int i = 0 ; i < array.length ; i++){
            mid[array[i] - min]++;
        }
        for(int i = 1 ; i < mid.length ; i++){
            mid[i] = mid[i-1] + mid[i];
        }
        int[] ans = new int[array.length];
        for(int i = 0 ; i < array.length ; i++){
            ans[mid[array[i] - min] - 1] = array[i];
            mid[array[i] - min]--;
        }
        for(int i = 0 ; i < ans.length ; i++){
            array[i] = ans[i];
        }
    }
    public static void main(String[] args){
        int[] array = {77 , 23 , 1 , -1 , 90 ,6 ,  11};
        sort(array);
        for(int i : array){
            System.out.print(i + ",");
        }
    }
}
